package zijie;

/**
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 */
public class FindMedianSortedArrays_4_6 {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1)/2;
        int right = (m + n + 2)/2;
        return (findKth(nums1,0,nums2,0,left) + findKth(nums1,0,nums2,0,right))/2.0;
    }
    int findKth(int[] nums1, int i , int[] nums2, int j, int k){
        if(i >= nums1.length) return nums2[j + k - 1];
        if(j >= nums2.length) return  nums1[i + k - 1];

        if(k == 1)  return Math.min(nums1[i], nums2[j]);

        int midVal1 = (i + k/2 - 1 < nums1.length) ? nums1[i + k/2 - 1]:Integer.MAX_VALUE;
        int midVal2 = (j + k/2- 1 < nums2.length) ? nums2[j + k/2 - 1]:Integer.MAX_VALUE;

        if(midVal1 < midVal2)
            return findKth(nums1, i + k/2, nums2, j, k - k/2);
        else
            return findKth(nums1, i, nums2, j + k/2, k - k/2);

    }
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[] res = new int[n + m];
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < n && j < m){
//            if(nums1[i]<nums1[j]){
//                res[k++] = nums1[i++];
//            }else{
//                res[k++] = nums2[j++];
//            }
            res[k++] = nums1[i] < nums2[j] ? nums1[i++]:nums2[j++];
        }
        while (j < m){
            res[k++] = nums2[j++];
        }
        while (i < n){
            res[k++] = nums1[i++];
        }

        if(k%2 == 0){
            return (float) (res[res.length/2-1] + res[res.length/2])/2;
        }else{
            return res[res.length/2];
        }

    }
}
